{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# SymbolicBayesTree"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "A `SymbolicBayesTree` is a tree structure where each node (`SymbolicBayesTreeClique`) represents a clique of variables that were eliminated together during multifrontal elimination. Unlike a `SymbolicJunctionTree` which stores factors, a `SymbolicBayesTree` stores the resulting `SymbolicConditional` for each clique.\n",
        "\n",
        "It represents the factored structure $P(X) = Π P(C_j | S_j)$, where $C_j$ are the frontal variables of clique $j$ and $S_j$ are its separator variables (parents in the Bayes Tree). This structure is computationally advantageous for inference, especially for calculating marginals or performing incremental updates (like in iSAM)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "<a href=\"https://colab.research.google.com/github/borglab/gtsam/blob/develop/gtsam/symbolic/doc/SymbolicBayesTree.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "tags": [
          "remove-cell"
        ]
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Note: you may need to restart the kernel to use updated packages.\n"
          ]
        }
      ],
      "source": [
        "%pip install --quiet gtsam-develop"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {},
      "outputs": [],
      "source": [
        "from gtsam import SymbolicFactorGraph, Ordering\n",
        "from gtsam.symbol_shorthand import X, L\n",
        "import graphviz # For visualization"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Creating a SymbolicBayesTree\n",
        "\n",
        "A Bayes tree is typically created by eliminating a `SymbolicFactorGraph` using the multifrontal method."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 20,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Create a factor graph from a GTSFM problem\n",
        "graph = SymbolicFactorGraph()\n",
        "\n",
        "edges = [(2, 4), (2, 5), (2, 27), (4, 6), (5, 6), (5, 7), (5, 8), (5, 9), (6, 7), (6, 8), (6, 9), \n",
        "         (7, 8), (7, 9), (8, 9), (9, 12), (9, 24), (9, 28), (10, 12), (10, 29), (20, 21), (20, 22), \n",
        "         (20, 23), (20, 24), (21, 22), (21, 23), (21, 24), (22, 23), (22, 24), (23, 24), (25, 26), \n",
        "         (25, 27), (25, 28), (25, 29), (26, 27), (26, 28), (26, 29), (27, 28), (27, 29), (28, 29)]\n",
        "\n",
        "for i,j in edges:\n",
        "    graph.push_factor(X(i), X(j))\n",
        "\n",
        "# Define an elimination ordering\n",
        "ordering = Ordering.MetisSymbolicFactorGraph(graph)  # Use METIS for this example\n",
        "\n",
        "# Eliminate using Multifrontal method\n",
        "bayes_tree = graph.eliminateMultifrontal(ordering)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Visualization and Properties\n",
        "\n",
        "The Bayes tree structure can be visualized, and we can query its properties."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 21,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "\n",
            "Bayes Tree size (number of cliques): 8\n",
            "Is the Bayes Tree empty? False\n"
          ]
        }
      ],
      "source": [
        "print(f\"\\nBayes Tree size (number of cliques): {bayes_tree.size()}\")\n",
        "print(f\"Is the Bayes Tree empty? {bayes_tree.empty()}\")"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 22,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "image/svg+xml": [
              "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
              "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
              " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
              "<!-- Generated by graphviz version 12.0.0 (0)\n",
              " -->\n",
              "<!-- Title: G Pages: 1 -->\n",
              "<svg width=\"695pt\" height=\"260pt\"\n",
              " viewBox=\"0.00 0.00 694.66 260.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
              "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 256)\">\n",
              "<title>G</title>\n",
              "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-256 690.66,-256 690.66,4 -4,4\"/>\n",
              "<!-- 20 -->\n",
              "<g id=\"node1\" class=\"node\">\n",
              "<title>20</title>\n",
              "<ellipse fill=\"none\" stroke=\"black\" cx=\"373.29\" cy=\"-234\" rx=\"114.82\" ry=\"18\"/>\n",
              "<text text-anchor=\"middle\" x=\"373.29\" y=\"-228.95\" font-family=\"Times,serif\" font-size=\"14.00\">x28, x25, x26, x9, x29, x27</text>\n",
              "</g>\n",
              "<!-- 21 -->\n",
              "<g id=\"node2\" class=\"node\">\n",
              "<title>21</title>\n",
              "<ellipse fill=\"none\" stroke=\"black\" cx=\"224.29\" cy=\"-162\" rx=\"70.29\" ry=\"18\"/>\n",
              "<text text-anchor=\"middle\" x=\"224.29\" y=\"-156.95\" font-family=\"Times,serif\" font-size=\"14.00\">x5, x4 : x9, x27</text>\n",
              "</g>\n",
              "<!-- 20&#45;&gt;21 -->\n",
              "<g id=\"edge1\" class=\"edge\">\n",
              "<title>20&#45;&gt;21</title>\n",
              "<path fill=\"none\" stroke=\"black\" d=\"M337.98,-216.41C316.8,-206.46 289.73,-193.74 267.31,-183.21\"/>\n",
              "<polygon fill=\"black\" stroke=\"black\" points=\"268.96,-180.12 258.42,-179.04 265.98,-186.46 268.96,-180.12\"/>\n",
              "</g>\n",
              "<!-- 25 -->\n",
              "<g id=\"node6\" class=\"node\">\n",
              "<title>25</title>\n",
              "<ellipse fill=\"none\" stroke=\"black\" cx=\"373.29\" cy=\"-162\" rx=\"60.56\" ry=\"18\"/>\n",
              "<text text-anchor=\"middle\" x=\"373.29\" y=\"-156.95\" font-family=\"Times,serif\" font-size=\"14.00\">x12 : x9, x29</text>\n",
              "</g>\n",
              "<!-- 20&#45;&gt;25 -->\n",
              "<g id=\"edge5\" class=\"edge\">\n",
              "<title>20&#45;&gt;25</title>\n",
              "<path fill=\"none\" stroke=\"black\" d=\"M373.29,-215.7C373.29,-208.41 373.29,-199.73 373.29,-191.54\"/>\n",
              "<polygon fill=\"black\" stroke=\"black\" points=\"376.79,-191.62 373.29,-181.62 369.79,-191.62 376.79,-191.62\"/>\n",
              "</g>\n",
              "<!-- 27 -->\n",
              "<g id=\"node8\" class=\"node\">\n",
              "<title>27</title>\n",
              "<ellipse fill=\"none\" stroke=\"black\" cx=\"569.29\" cy=\"-162\" rx=\"117.37\" ry=\"18\"/>\n",
              "<text text-anchor=\"middle\" x=\"569.29\" y=\"-156.95\" font-family=\"Times,serif\" font-size=\"14.00\">x24, x23, x22, x21, x20 : x9</text>\n",
              "</g>\n",
              "<!-- 20&#45;&gt;27 -->\n",
              "<g id=\"edge7\" class=\"edge\">\n",
              "<title>20&#45;&gt;27</title>\n",
              "<path fill=\"none\" stroke=\"black\" d=\"M417.76,-217.12C446.26,-206.94 483.45,-193.66 513.86,-182.79\"/>\n",
              "<polygon fill=\"black\" stroke=\"black\" points=\"514.64,-186.23 522.89,-179.57 512.29,-179.64 514.64,-186.23\"/>\n",
              "</g>\n",
              "<!-- 22 -->\n",
              "<g id=\"node3\" class=\"node\">\n",
              "<title>22</title>\n",
              "<ellipse fill=\"none\" stroke=\"black\" cx=\"70.29\" cy=\"-90\" rx=\"70.29\" ry=\"18\"/>\n",
              "<text text-anchor=\"middle\" x=\"70.29\" y=\"-84.95\" font-family=\"Times,serif\" font-size=\"14.00\">x2 : x4, x5, x27</text>\n",
              "</g>\n",
              "<!-- 21&#45;&gt;22 -->\n",
              "<g id=\"edge2\" class=\"edge\">\n",
              "<title>21&#45;&gt;22</title>\n",
              "<path fill=\"none\" stroke=\"black\" d=\"M190.87,-145.81C168.45,-135.62 138.67,-122.08 114.32,-111.01\"/>\n",
              "<polygon fill=\"black\" stroke=\"black\" points=\"115.83,-107.86 105.28,-106.91 112.94,-114.23 115.83,-107.86\"/>\n",
              "</g>\n",
              "<!-- 23 -->\n",
              "<g id=\"node4\" class=\"node\">\n",
              "<title>23</title>\n",
              "<ellipse fill=\"none\" stroke=\"black\" cx=\"224.29\" cy=\"-90\" rx=\"65.68\" ry=\"18\"/>\n",
              "<text text-anchor=\"middle\" x=\"224.29\" y=\"-84.95\" font-family=\"Times,serif\" font-size=\"14.00\">x6 : x4, x5, x9</text>\n",
              "</g>\n",
              "<!-- 21&#45;&gt;23 -->\n",
              "<g id=\"edge3\" class=\"edge\">\n",
              "<title>21&#45;&gt;23</title>\n",
              "<path fill=\"none\" stroke=\"black\" d=\"M224.29,-143.7C224.29,-136.41 224.29,-127.73 224.29,-119.54\"/>\n",
              "<polygon fill=\"black\" stroke=\"black\" points=\"227.79,-119.62 224.29,-109.62 220.79,-119.62 227.79,-119.62\"/>\n",
              "</g>\n",
              "<!-- 24 -->\n",
              "<g id=\"node5\" class=\"node\">\n",
              "<title>24</title>\n",
              "<ellipse fill=\"none\" stroke=\"black\" cx=\"224.29\" cy=\"-18\" rx=\"80.01\" ry=\"18\"/>\n",
              "<text text-anchor=\"middle\" x=\"224.29\" y=\"-12.95\" font-family=\"Times,serif\" font-size=\"14.00\">x8, x7 : x5, x6, x9</text>\n",
              "</g>\n",
              "<!-- 23&#45;&gt;24 -->\n",
              "<g id=\"edge4\" class=\"edge\">\n",
              "<title>23&#45;&gt;24</title>\n",
              "<path fill=\"none\" stroke=\"black\" d=\"M224.29,-71.7C224.29,-64.41 224.29,-55.73 224.29,-47.54\"/>\n",
              "<polygon fill=\"black\" stroke=\"black\" points=\"227.79,-47.62 224.29,-37.62 220.79,-47.62 227.79,-47.62\"/>\n",
              "</g>\n",
              "<!-- 26 -->\n",
              "<g id=\"node7\" class=\"node\">\n",
              "<title>26</title>\n",
              "<ellipse fill=\"none\" stroke=\"black\" cx=\"373.29\" cy=\"-90\" rx=\"65.17\" ry=\"18\"/>\n",
              "<text text-anchor=\"middle\" x=\"373.29\" y=\"-84.95\" font-family=\"Times,serif\" font-size=\"14.00\">x10 : x12, x29</text>\n",
              "</g>\n",
              "<!-- 25&#45;&gt;26 -->\n",
              "<g id=\"edge6\" class=\"edge\">\n",
              "<title>25&#45;&gt;26</title>\n",
              "<path fill=\"none\" stroke=\"black\" d=\"M373.29,-143.7C373.29,-136.41 373.29,-127.73 373.29,-119.54\"/>\n",
              "<polygon fill=\"black\" stroke=\"black\" points=\"376.79,-119.62 373.29,-109.62 369.79,-119.62 376.79,-119.62\"/>\n",
              "</g>\n",
              "</g>\n",
              "</svg>\n"
            ],
            "text/plain": [
              "<graphviz.sources.Source at 0x1120de8a0>"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "# Visualize the Bayes tree using graphviz\n",
        "display(graphviz.Source(bayes_tree.dot()))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Traversing a Bayes Tree"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 23,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Number of roots: 1\n",
            "\n",
            "Clique:\n",
            " P( x28 x25 x26 x9 x29 x27)\n",
            "\n",
            "Clique:\n",
            " P( x5 x4 | x9 x27)\n",
            "\n",
            "Clique:\n",
            " P( x2 | x4 x5 x27)\n",
            "\n",
            "Clique:\n",
            " P( x6 | x4 x5 x9)\n",
            "\n",
            "Clique:\n",
            " P( x8 x7 | x5 x6 x9)\n",
            "\n",
            "Clique:\n",
            " P( x12 | x9 x29)\n",
            "\n",
            "Clique:\n",
            " P( x10 | x12 x29)\n",
            "\n",
            "Clique:\n",
            " P( x24 x23 x22 x21 x20 | x9)\n"
          ]
        }
      ],
      "source": [
        "roots = bayes_tree.roots()\n",
        "print(f\"Number of roots: {len(roots)}\")\n",
        "\n",
        "def traverse_clique(clique):\n",
        "    if clique:\n",
        "        clique.print(\"\\nClique:\\n\")\n",
        "        for j in range(clique.nrChildren()):\n",
        "            traverse_clique(clique[j])\n",
        "\n",
        "for root in roots:\n",
        "    traverse_clique(root)"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "py312",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.12.6"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 4
}
